\section{研究背景}

随着大数据时代的到来,数据的规模以前所未有的速度增长着, Facebook、Twitter、微博等社交媒体每天都产生大量的社交图数据。
如何处理如此大规模的图数据成为目前研究的热点。
其中,图划分问题又是图数据处理领域中最为重要的问题之一,图的搜索,模式匹配等算法都需要图划分算法的支持。
本文依托近些年来兴起的大数据平台,利用其提供强大的存储与计算能力,研究并实现了以大数据处理平台Spark作为处理引擎的图划分算法。


图作为一种由顶点和边构成的数据结构,能够简洁有力的表达事物之间的联系。
在今天这个信息化社会中，随着互联网用户的急剧增加，越来越多的网络数据问题摆在了我们面前。
而在大数据时代下，大规模图数据处理问题便是一大热点。
类似于网状图，如果将每个网络用户看作图中的节点，而将用户与用户之间的关系看作图中的边，那么整个网络就可看作一张网络图，大量的网络图组成的集合便是图数据。

图划分是经典的组合优化问题，它的应用背景极其广泛，包括软硬件协同设计、VLSI 设计、并行计算中的任务分配等众多领域。
图划分是把一个图的顶点集分成$k$个不相交的子集，且满足子集之间的某些限制，即要找到一个图的划分，使得连接不同群组的边的权重尽可能小（意味着不同类中的点之间是不同的），而在群组内部的边有着很高的权重（意味着相同类中的点是彼此相似的）。
近年来，计算机技术正以难以想象的速度发展，继而各个领域的问题变得日益复杂（比如软硬件划分、大规模集成电路设计、任务分配等），因此，人们迫切地需要对图划分进行深入而广泛的研究。

考虑到大量图数据的实时性需求，我们采用了Spark框架进行实验。
Apache Spark是一个围绕速度、易用性和复杂分析构建的大数据处理框架。
Spark最初在2009年由加州大学伯克利分校的AMPLab开发，并于2010年成为Apache的开源项目之一。
与Hadoop和Storm等其他大数据和MapReduce技术相比，Spark有如下优势：

\begin{itemize}
    \item Spark提供了一个全面、统一的框架用于管理各种有着不同性质（文本数据、图表数据等）的数据集和数据源（批量数据或实时的流数据）的大数据处理的需求
    \item Spark可以将Hadoop集群中的应用在内存中的运行速度提升100倍，甚至能够将应用在磁盘上的运行速度提升10倍
\end{itemize}

本文综合前人的研究，首先介绍图划分算法的研究现状，重点介绍几类典型的图划分算法。
然后,通过对比实验，分析、比较不同图划分算法的性能特点。
最后，对图划分算法进行总结。
